package com.example.demo.sf;


import java.util.Arrays;

/**
 * 二分查找法
 */
public class BinarySearch {

    public static void main(String[] args) {
        int[] arr = {1,2,3,4,6};
//        System.out.println(Arrays.binarySearch(arr,12)); // 12 是没有的 应该插入到10 的后边 也就是index=9 的位置，取相反数在减去1 就是 -10
//        System.out.println(Arrays.binarySearch(arr,8));// 8 是没有的 应该插入到7 的后边 也就是index=7 的位置，取相反数在减去1 就是 -8
//        System.out.println(binarySearch(arr,9));
        System.out.println(binarySearchRightMost2(arr,5));

    }

    /**
     *  二分查找最左边的索引
     *  当一个排好序的数组  中存在多个相同的元素，找出最右边的索引，找不到就返回该目标值需要插入的索引  1235
     * @param arr
     * @param target
     * @return
     */
    public static int binarySearchRightMost2(int[] arr,int target) {
        int left = 0;
        int right = arr.length-1 ;
        while (left <= right) {
            int mid = (left + right) >>> 1;
            if (arr[mid] <= target) {
                left = mid + 1;
            }else{
                right = mid - 1;
            }
        }
        return left -1;
    }

    /**
     *  二分查找最左边的索引
     *  当一个排好序的数组  中存在多个相同的元素，找出最左边的索引，找不到就返回该目标值需要插入的索引  1235
     * @param arr
     * @param target
     * @return
     */
    public static int binarySearchLeftMost2(int[] arr,int target) {
        int left = 0;
        int right = arr.length-1 ;
        while (left <= right) {
            int mid = (left + right) >>> 1;
            if ( target < arr[mid] ) {
                right = mid - 1;
            }else{

                left = mid + 1;
            }
        }
        return left;
    }

    /**
     *  二分查找最左边的索引
     *  当一个排好序的数组  中存在多个相同的元素，找出最左边的索引  找不到返回 -1
     * @param arr
     * @param target
     * @return
     */

    public static int binarySearchLeftMost(int[] arr,int target) {
        int left = 0;
        int right = arr.length-1 ;
        int contined = -1;
        while (left <= right) {
            int mid = (left + right) >>> 1;
            if (arr[mid] < target) {
                left = mid + 1;
            }else if(arr[mid] > target){
                right = mid - 1;
            }else{
                contined = mid;
                right = mid - 1;
            }
        }
        return contined;
    }

    public static int binarySearch(int[] arr,int target) {
        int left = 0;
        int right = arr.length;
        while (left < right) {
            int mid = (left + right) >>> 1;
            if (arr[mid] == target) {
                return mid;
            } else if (arr[mid] > target) {
                right = mid;
            } else {
                left = mid + 1;
            }

        }
        return -1;
    }

}
